/* This program calculates the selection of coins needed to return change based
 * on the coins available */
#include <stdio.h>

/* We cheat. Infinity is >= 9999 */
#define INFINITY 9999

/* Set of coins - (value, count) */
int coins[][2] = 
{
    {1, 4},
    {3, 1},
    {4, 1},
    {5, 1},
};

/* Number of denominations */
int num = 4;

int counts[100];

/* used[i][j] tells us how many coins of denom i were used to achieve sum j */
int used[100][100];
int dp[100][100];


/* Print a (m x n) array */
void print_arr(int arr[][100], int m, int n)
{
    int i,j;

    printf("%6d | ",0);
    for(j=0;j<n;j++)
    {
        printf("%6d ",j);
    }
    printf("\n----------------------------------------------------------------------------------------\n");

    for (i=0; i<m; i++)
    {
        printf("%6d | ",coins[i][0]);
        for (j=0; j<n; j++)
        {
            printf("%6d ", arr[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}


void initialize(int sum, int k)
{
    int i, j;

    /* Initialize the dynamic programming array with a set of 1 coin of denom
     * 1. We need j coins to realise sum j. If j is greater than available
     * coins, then its not possible. i.e. we need INFINITY coins */
    /* TODO: Fix this for when 1st coin is not of denom 1 */
    for(j=1; j<=sum; j++)
    {
        dp[0][j] = (j>coins[0][1]) ? INFINITY : j;
        if(dp[0][j] == INFINITY)
        {
            used[0][j] = 0;
        }
        else
        {
            used[0][j] = j;
        }

    }

    /* To realise a sum of 0, we need 0 coins for any denomination */
    for (i=0; i<k; i++)
    {
        dp[i][0] = 0;
    }
}


void change(int sum, int k)
{
    int i,j;
    for (i=1; i<k; i++)
    {
        for ( j=1; j<=sum; j++)
        {
            /* The current coin being considered is greater than the current
             * sum. We can't add it */
            if (coins[i][0] > j)
            {
                dp[i][j] = dp[i-1][j];
                used[i][j] = 0;
            }
            else 
            {
                /* Compare adding the coin or not adding it. 
                   We know that the current sum can be realised by using coins
                   from only from the set 0-i-1. That value is saved in (i-1,j)
                   If we are to use the current coin and realise this sum we
                   have to add it to the value of (sum - current coin) realised
                   with 0..i-1 coins
                 */
                int prev_min = dp[i-1][j];
                int new_min = 1 + dp[i-1][j-coins[i][0]];

                if(new_min < prev_min)
                {
                    /* Adding the new coin is better than the previous min */
                    int needed = used[i][j-coins[i][0]] + 1;
                    if (needed <= coins[i][1])
                    {
                        dp[i][j] = dp[i][j-coins[i][0]]+1;
                        used[i][j] = needed;
                    }
                    else
                    {
                        dp[i][j] = dp[i-1][j-coins[i][0]]+1;
                        used[i][j] = 1;
                    }
                }
                else
                {
                    dp[i][j]= prev_min;
                    used[i][j] = 0;
                }


            }
        }
    }
}

void retrace(int sum, int k)
{
    int i=k,j=sum;
    int x;

    if (dp[i][j] >= INFINITY)
    {
        printf("\n!!No solution\n");
        return;
    }

    if(sum==0)
    {
        printf("\n");
        return;
    }

    if (used[i][j] == 0)
    {
        retrace(sum, k-1);
    }
    else
    {
        for(x = used[i][j]; x>0; x--)
        {
            printf("%d ",coins[i][0]);
        }

        retrace(sum - (coins[i][0] * used[i][j]), k-1);
    }
}


int main(int argc, char **argv)
{
    int sum = 17, num=4;

    printf("Enter sum to test: ");
    scanf("%d", &sum);

    initialize(sum,num);
    change(sum,num);
    //print_arr(dp,num,sum+1);
    //print_arr(used,num,sum+1);

    retrace(sum, num-1);

    return 0;
}

